<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
    <title>min_lcost_cflow</title>
  </head>
  <body bgcolor="#FFFFFF">
    <center>Scilab function</center>
    <div align="right">Last update : September 1995</div>
    <p>
      <b>min_lcost_cflow</b> -  minimum linear cost constrained flow</p>
    <h3>
      <font color="blue">Calling Sequence</font>
    </h3>
    <dl>
      <dd>
        <tt>[c,phi,v,flag] = min_lcost_cflow(i,j,cv,g)  </tt>
      </dd>
    </dl>
    <h3>
      <font color="blue">Parameters</font>
    </h3>
    <ul>
      <li>
        <tt>
          <b>i</b>
        </tt>: integer, source node number</li>
      <li>
        <tt>
          <b>j</b>
        </tt>: integer, sink node number</li>
      <li>
        <tt>
          <b>cv</b>
        </tt>: scalar, value of constrained flow</li>
      <li>
        <tt>
          <b>g</b>
        </tt>: graph list</li>
      <li>
        <tt>
          <b>c</b>
        </tt>: value of cost</li>
      <li>
        <tt>
          <b>phi</b>
        </tt>: row vector of the values of flow on the arcs</li>
      <li>
        <tt>
          <b>v</b>
        </tt>: value of flow from source to sink</li>
      <li>
        <tt>
          <b>flag</b>
        </tt>: feasible constrained flow flag (0 or 1)</li>
    </ul>
    <h3>
      <font color="blue">Description</font>
    </h3>
    <p>
      <tt>
        <b>min_lcost_cflow</b>
      </tt> computes the minimum cost flow in the network <tt>
        <b>g</b>
      </tt>, 
    with the value of the flow from source node <tt>
        <b>i</b>
      </tt> to 
    sink node <tt>
        <b>j</b>
      </tt> constrained to be equal to <tt>
        <b>cv</b>
      </tt>.</p>
    <p>
      <tt>
        <b>min_lcost_cflow</b>
      </tt> returns the total cost of the flows on the arcs <tt>
        <b>c</b>
      </tt>,
    the row vector of the flows on the arcs <tt>
        <b>phi</b>
      </tt> and the value of the flow 
    <tt>
        <b>v</b>
      </tt> on the virtual arc from sink to source. If <tt>
        <b>v</b>
      </tt> is less than 
    <tt>
        <b>cv</b>
      </tt>, a message is issued, but the computation is done: in this
    case <tt>
        <b>flag</b>
      </tt> is equal to 0, otherwise it is equal to 1.</p>
    <p>
    The bounds of the flows are given by the elements <tt>
        <b>edge_min_cap</b>
      </tt> and
    <tt>
        <b>edge_max_cap</b>
      </tt> of the graph list. 
    The value of the minimum capacity must be equal to zero, and the value 
    of the maximum capacity must be non negative and must be integer
    numbers.
    If the value of <tt>
        <b>edge_min_cap</b>
      </tt> or <tt>
        <b>edge_max_cap</b>
      </tt> is not given (empty
    row vector <tt>
        <b>[]</b>
      </tt>), it is assumed to be equal to 0 on each edge.</p>
    <p>
    The costs on the edges are given by the element <tt>
        <b>edge_cost</b>
      </tt> of the 
    graph list.
    The costs must be non negative.
    If the value of <tt>
        <b>edge_cost</b>
      </tt> is not given (empty row vector <tt>
        <b>[]</b>
      </tt>), 
    it is assumed to be equal to 0 on each edge.</p>
    <p>
    The demands, element <tt>
        <b>node_demand</b>
      </tt> of the graph list, must be
    equal to zero.</p>
    <p>
    This function uses the algorithm of Busacker and Goven.</p>
    <h3>
      <font color="blue">Examples</font>
    </h3>
    <pre>

ta=[1 1 2 2 2 3 4 4 5 6 6 6 7 7 7 8 9 10 12 12 13 13 13 14 15 14 9 11 10];
he=[2 6 3 4 5 1 3 5 1 7 10 11 5 8 9 5 8 11 10 11 9 11 15 13 14 4 6 9 1];
g=make_graph('foo',1,15,ta,he);
g('node_x')=[194 191 106 194 296 305 305 418 422 432 552 550 549 416 548];
g('node_y')=[56 181 276 278 276 103 174 281 177 86 175 90 290 397 399];
show_graph(g);
g1=g; ma=arc_number(g1); n=g1('node_number');
g1('edge_min_cap')=0*ones(1,ma);
rand('uniform');
g1('edge_max_cap')=round(20*rand(1,ma))+ones(1,ma);
g1('edge_cost')=10*rand(1,ma)+ones(1,ma);
source=15; sink=1; cv=5;
[c,phi,v]=min_lcost_cflow(source,sink,cv,g1);
x_message(['The cost is: '+string(c);
           'Showing the flow on the arcs']);
nodetype=0*ones(1,n); nodetype(source)=2; nodetype(sink)=1;
g1('node_type')=nodetype;
ii=find(phi&lt;&gt;0); edgecolor=phi; edgecolor(ii)=11*ones(ii);
g1('edge_color')=edgecolor;
edgefontsize=8*ones(1,ma); edgefontsize(ii)=18*ones(ii);
nodecolor=0*ones(1,n); nodecolor(source)=11; nodecolor(sink)=11;
g1('node_color')=nodecolor;
g1('edge_font_size')=edgefontsize;
g1('edge_label')=string(phi);
show_graph(g1);
 
  </pre>
    <h3>
      <font color="blue">See Also</font>
    </h3>
    <p>
      <a href="min_lcost_flow1.htm">
        <tt>
          <b>min_lcost_flow1</b>
        </tt>
      </a>,&nbsp;&nbsp;<a href="min_lcost_flow2.htm">
        <tt>
          <b>min_lcost_flow2</b>
        </tt>
      </a>,&nbsp;&nbsp;<a href="min_qcost_flow.htm">
        <tt>
          <b>min_qcost_flow</b>
        </tt>
      </a>,&nbsp;&nbsp;</p>
  </body>
</html>
